1. Field of the Invention
The present invention relates generally to the field of hardware and software for computer network communications, and more specifically to the field of buffering the data involved in network connections, particularly in asynchronous transfer mode (ATM) switches or any other fast network environment.
2. Description of the Background Art
Network communication systems interconnect many users in a network. Each user is connected to the network at a port. The network is formed by the interconnection of many nodes where information input at an input port from one user at a source is passed from node to node through the network to an output port and to another user at a destination. The information transferred from source to destination is packetized and each node switches incoming packets at incoming ports to outgoing packets at outgoing ports.
Fast packet switches at the nodes may transfer hundreds of thousands of packets per second at every switch port. Switch sizes range from a few ports to thousands of ports. The term xe2x80x9cfast packet switchxe2x80x9d includes switches capable of handling both variable-length packets and fixed-length packets. Fixed-length packets are desirable since they simplify the switch design. Fast packet switches using short, fixed-length packets (cells) are referred to as asynchronous transfer mode (ATM) switches. Fast packet switches handle different types of communications services in a single integrated network where such services may include voice, video and data communications. Since voice and video services can tolerate only a limited amount of delay and delay variance through a network, ATM switches are especially suitable for such services. The ATM standard for broadband networks defines a cell having a length of 53 bytes with a header of 5 bytes and data of 48 bytes.
In a typical ATM switch, the cell processing functions are performed within the nodes of a network. Each node is an ATM switch, which includes input controllers, a switch fabric, output controllers and a node control. The node control is used for functions including connection establishment and release, bandwidth reservation, congestion control, maintenance and network management.
Cell arrivals in an ATM switch are not scheduled. Typically, a number of cells may arrive simultaneously at different input ports each requesting the same output port. Operations in which requests exceeding the output capacity of the output port are referred to as output contention (or conflict). Since an output port can only transmit a fixed number of cells at a time, only the fixed number of cells can be accepted for transmission, so that any other cells routed to that port must either be discarded or buffered in a queue. When the traffic load exceeds the available system resources at a switch, connections are refused, performance degrades, and congestion results.
Congestion can be brought about by several factors. If nodes in a network are too slow to perform the various tasks required of them (queuing-buffers, updating tables, etc.), queues build up, even though excess line capacity exists. If a node does not have sufficient buffer resource to support the estimated load of a pending call, the node will block the call. One available congestion control technique to address this problem is that of preallocating resources. When a channel is set up (commonly referred to as a xe2x80x9cvirtualxe2x80x9d channel, since the set up is only planned until the data is actually forwarded), a call request travels through the network making table entries at each node that controls the route to be followed by subsequent traffic. In preallocating, each call request reserves one or more data buffers in each node unless all the buffers are already reserved. If all buffers are reserved, another route is found or a xe2x80x9cbusy signalxe2x80x9d is returned to the source. If buffers are reserved for each channel in each node, there is always a place to store any incoming packet to that node. One problem with preallocation is that substantial buffer resources are allocated to specific virtual channel connections, regardless of whether there is any traffic over the virtual channel. An inefficient use of resources results, particularly for buffer resources, since resources not being used by the connection to which they are allocated are nevertheless unavailable to other virtual channels.
This problem is exacerbated in ATM networks due to the required data type characteristics. The ATM Forum Traffic Management Specification, version 4.0 [ATMF96b, af-tm-0056.000, April, 1996, incorporated herein by reference), defines five service categories: Constant Bit Rate (xe2x80x9cCBRxe2x80x9d), Variable Bit Rate realtime (xe2x80x9cVBRrtxe2x80x9d), Variable Bit Rate non-realtime (xe2x80x9cVBRnrtxe2x80x9d), Unspecified Bit Rate (xe2x80x9cUBRxe2x80x9d), and Available Bit Rate (xe2x80x9cABRxe2x80x9d).
The CBR service category, which resembles leased-line services, is used for connections needing a static amount of bandwidth continuously throughout the connection. CBR is characterized by its Peak Cell Rate (PCR). Typical applications include voice and video, including videoconferencing and audio/video distribution and retrieval (television, distance learning, pay-per-view, video-on-demand, and audio library). CBR uses a static amount of bandwidth continuously throughout the life of the connection.
The VBRrt service category supplies tightly constrained delay and delay variation, but not necessarily a fixed transmission rate. VBRrt connections are characterized by their PCR, Sustained Cell Rate (SCR), and Maximum Burst Size (MBS). Applications include native ATM voice with bandwidth compression and silence suppression, and some types of multimedia communications.
The VBRnrt service category is intended for non-realtime bursty traffic that requires service guarantees, such as frame relay traffic. Like VBRrt, VBRnrt connections are also characterized in terms of PCR, SCR and MBS. Typical applications include loss-sensitive/delay-insensitive transaction processing (airline reservations, banking transactions, process monitoring) and frame relay internetworking.
The UBR service category, sometimes referred to as a best-effort service, is intended for non-realtime, bursty applications. These include text, data, and image transfer, which are tolerant to delay and loss, including telecommuting, email, and supercomputer applications such as remote procedure calls, distributed file services, and computer process swapping and paging. Other examples include LAN emulation and applications such as LAN interconnecting and internetworkingxe2x80x94which run over router-based protocols like Transmission Control Protocol/Internet
The ABR service category provides a Minimum Cell Rate (MCR) plus any available bandwidth. ABR connections are characterized by both a PCR and an MCR, and are used by applications that can adapt to network feedback. A flow-control mechanism fairly allocates the available bandwidth among ABR connections. Applications are similar to those for UBR. ABR traffic is supplied an MCR and any available bandwidth, while UBR traffic does not require that switches use specified cell rates in negotiating bandwidth.
At all times, but of particular import during periods of congestion, switching priority is given to the xe2x80x9cguaranteedxe2x80x9d data types, including CBR, VBRrt, VBRnrt, and ABR (but only ABR below the MCR), while UBR and the remaining ABR traffic (above the MCR) gets access only to remaining available (xe2x80x9cnon-guaranteedxe2x80x9d) bandwidth after guaranteed connection contracts are fulfilled. When sufficient buffer resources are unavailable, the ATM switch will block pending connections.
Such specific constraints on traffic flow, priority, and timing result in a need for a system which determines how large queues should be allowed to grow (per-connection) within the shared buffer. Queue lengths for delay-sensitive traffic (CBR and VBRrt) should be tightly constrained in order to bound worst-case delay. Conversely, queue lengths for delay-insensitive traffic (VBRnrt, ABR, UBR) should be allowed to grow to be very large, if necessary, in order to maximize throughput while minimizing loss. As such, it is essential that the buffer be partitioned so that some percentage of the shared buffer is always available for arriving cells from connections in guaranteed classes.
There is therefore a need in the art for a method and system of switch buffer management and node control which adheres to the appropriate data traffic priority hierarchy, while efficiently utilizing available buffer space to minimize congestion and provide a high level of adaptivity to changing connection-level loading patterns. There is a further need for such a method and system which can support a user""s loss and delay objectives for traffic requiring service guarantees at all times, and provides graceful performance degradation when the device is operating while congested.
To address the shortcomings of the available art, the present invention provides a switch for providing buffered connections within a computer data network, said switch having a plurality of input ports and at least one output port, the switch comprising: a buffer, storing at least a first data type received at a first input port and a second data type received at a second input port, the first data type having a higher priority level for storage in said buffer than said second data type, and a controller for partitioning said buffer into a first storage area for said first data type and a second storage area for said second data type, wherein said controller can partition said buffer in at least two manners, and where at least one the manners may be static partitioning, at least one of the manners may be adaptive partitioning, or the two manners may be both static partitioning and adaptive partitioning.
The invention further provides, in a switch for completing connections within a computer data network, said switch having a plurality of input ports and at least one output port, a method of buffering a connection, the method comprising the steps of: setting a partition within a data buffer to a first position, the partition dividing storage area in the buffer among a first data type and a second data type and thereby designating a maximum amount of said first data type the buffer can store, measuring the data load of the first data type at a first time, designating a first data type load high-tolerance level relative to the maximum and a first data type load low-tolerance level relative to the data load measured at the first time, measuring the data load of the first data type at a second time, if the data load measured at the second time is at least the load high-tolerance level, adjusting the partition to a second position, thereby increasing the maximum amount of said first data type the buffer can store, and if the data load measured at the second time is less than or equal to the load low-tolerance level, adjusting the partition to a second position, thereby decreasing the maximum amount of said first data type the buffer can store. The invention still further provides a computer implemented system for implementing the steps recited for this method.